package com.leetcode.contest;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author `RKC`
 * @date 2021/11/8 12:06
 */
public class LC5921最大化一张图中的路径价值 {

    private static int answer = 0;

    public static int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        //visited记录节点访问次数
        int[] visited = new int[values.length];
        int[][] matrix = new int[values.length][values.length];
        for (int i = 0; i < values.length; i++) {
            for (int j = 0; j < values.length; j++) {
                if (i == j) matrix[i][j] = 0;
                else matrix[i][j] = Integer.MAX_VALUE;
            }
        }
        //构建无向图，邻接矩阵表示
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            matrix[u][v] = matrix[v][u] = w;
        }
        int[] distances = dijkstra(matrix, 0);
        dfs(0, 0, maxTime, 0, values, matrix, visited, distances);
        return answer;
    }

    private static void dfs(int u, int curCostTime, int maxTime, int curValue, int[] values, int[][] matrix, int[] visited, int[] distances) {
        //超出规定时间，直接返回；如果当前消耗的时间加上回去的时间超出，也不能继续
        if (curCostTime > maxTime || curCostTime + distances[u] > maxTime) return;
        //当前节点访问次数加1
        visited[u]++;
        if (visited[u] == 1) curValue += values[u];
        //只有回到起始节点，记录当前经过所得到的最大价值
        if (u == 0) answer = Math.max(answer, curValue);
        //从当前节点u出发，到达其余相邻节点
        for (int v = 0; v < values.length; v++) {
            if (matrix[u][v] == Integer.MAX_VALUE || u == v) continue;
            //u能连通v节点
            dfs(v, curCostTime + matrix[u][v], maxTime, curValue, values, matrix, visited, distances);
        }
        //回溯
        visited[u]--;
    }

    private static int[] dijkstra(int[][] matrix, int u) {
        int[] distances = new int[matrix.length];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[u] = 0;
        PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparingInt(o -> o[1]));
        minHeap.offer(new int[]{u, 0});
        while (!minHeap.isEmpty()) {
            int[] cur = minHeap.poll();
            int v = cur[0], w = cur[1];
            for (int i = 0; i < matrix[0].length; i++) {
                if (matrix[v][i] == Integer.MAX_VALUE) continue;
                int dis = w + matrix[v][i];
                if (dis < distances[i]) {
                    minHeap.add(new int[]{i, dis});
                    distances[i] = dis;
                }
            }
        }
        return distances;
    }

    public static void main(String[] args) {
        int[] values = {5, 10, 15, 20};
        int[][] edges = {{0, 1, 10}, {1, 2, 10}, {0, 3, 10}};
        int maxTime = 30;
        System.out.println(maximalPathQuality(values, edges, maxTime));
    }
}
